﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GKS.Extensions.String.PatternMatching {
    
    /// <summary>
    /// A class that contains the implementation of the naiv pattern matching algorithm. 
    /// For a brief introduction to this algorithm visit http://en.wikipedia.org/wiki/String_searching_algorithm#Na.C3.AFve_string_search
    /// </summary>
    public static class NaivPatternMatching {

        /// <summary>
        /// The implementation of the naiv pattern matching algorithm.
        /// </summary>
        /// <param name="text">This string. The text that may contain the string we are looking for.</param>
        /// <param name="pattern">The string we are looking for.</param>
        /// <returns>The positions in which the text contains the pattern.</returns>
        public static int[] NaivMethod(this string text, string pattern, out int numberOfComparisons) {
            numberOfComparisons = 0;
            List<int> positions = new List<int>();
            int lastTextIndex = text.Length - pattern.Length + 1;   // the last position to start the comparisons in the text 
            int j;

            if (text.Length >= pattern.Length) {    // do the search only if the pattern is not longer than the text
                for (int i = 0; i < lastTextIndex; i++) {     // sliding through the text's characters
                    j = 0;

                    while (pattern.ElementAt(j).Equals(text.ElementAt(i + j))) {    // comparing the characters of the text with the characters of the pattern
                        numberOfComparisons++;

                        if (j++ == pattern.Length - 1) {      
                            // we are at the last character of the pattern
                            // we found a match
                            positions.Add(i);       // add the position we started from to the list of the positions of the matches
                            break;
                        }
                    }

                    numberOfComparisons += j == pattern.Length ? 1 : 2;
                }
            }

            return positions.ToArray();
        }
    }
}
